import java.util.ArrayList;
import java.util.List;

public class Tree {
	public static void main(String[] args){
		Tree tree= new Tree();
		
		Node root = tree.initialize();
		
		System.out.println(tree.inorderTraverse(root));
//		Node head = tree.convert(root);
//		while(head != null){
//			System.out.print(head.toString()+" ");
//			head = head.right;
//		}
//		System.out.println();
	}
	
	/**
	 *       1
	 *     /    \
	 *    2      3
	 *   / \    / \
	 *  4   5   9  10
	 *     / \
	 *    6   8
	 *   /   / \
	 *  7   11   12 
	 *  
	 * @return
	 */
	public Node initialize(){
		Node a = new Node(1);
		Node b = new Node(2);
		Node c = new Node(3);
		Node d = new Node(4, null, null);
		Node e = new Node(5);
		Node f = new Node(6);
		Node g = new Node(7,null,null);
		Node h = new Node(8);
		Node i = new Node(9,null,null);
		Node j = new Node(10,null,null);
		Node k = new Node(11,null,null);
		Node l = new Node(12,null,null);
		
		a.left = b;
		a.right = c;
		b.left = d;
		b.right = e;
		c.left = i;
		c.right = j;
		e.left = f;
		e.right = h;
		f.left = g;
		f.right = null;
		h.left = k;
		h.right = l;
		
		return a;
	}
	
	public List<Node> inorderTraverse(Node root){
		if (root == null)
			return null;
		
		List<Node> leftList = inorderTraverse(root.left);
		if (leftList == null) 
			leftList = new ArrayList<Node>();
		leftList.add(root);
		
		List<Node> rightList = inorderTraverse(root.right);
		if (rightList!= null)
			leftList.addAll(rightList);
		
		return leftList;
	}
	
	public Node convert(Node root){
		Node head = convert2(root);
		head.left.right = null;
		head.left = null;
		return head;
	}
	
	public Node convert2(Node root){
		if (root == null)
			return null;
		
		Node left = convert2(root.left);
		Node right = convert2(root.right);
		
		if (left == null && right == null){
			root.left = root;
			root.right = root;
			return root;
		}
		
		Node tail = right == null? root: right.left;
		
		if (left == null)
			concat(right.left, root);
		else 
			concat(left.left, root);
		
		if (right == null)
			concat(root, left);
		else
			concat(root, right);
		
		if (left != null && right != null){
			concat(tail, left);
		}
		
		return left == null ? root: left;
	}
	
	private void concat(Node x, Node y){
		x.right = y;
		y.left = x;
	}

	public boolean isSubtree(Node t1, Node t2) {
		if (t1 == null && t2 == null)
			return true;
		if (t1 == null && t2 != null)
			return false;
		if (t1 != null && t2 == null)
			return true;

		boolean isSubtree = checkSubtree(t1, t2);
		if (isSubtree)
			return true;

		return checkSubtree(t1.left, t2) || checkSubtree(t1.right, t2);
	}

	public boolean checkSubtree(Node t1, Node t2) {
		if (t1 == null && t2 == null)
			return true;

		if (t1 == null)
			return false;
		if (t2 == null)
			return false;

		if (t1.val != t2.val)
			return false;
		else
			return checkSubtree(t1.left, t2.left)
					&& checkSubtree(t1.right, t2.right);
	}
}

class Node {
	int val;
	Node left;
	Node right;
	
	public Node (int val){
		this.val = val;
	}
	
	public Node (int val, Node left, Node right){
		this.val = val;
		this.left = left;
		this.right = right;
	}
	
	@Override
	public String toString(){
		return String.valueOf(val);
	}
	
	public boolean isLeaf(){
		return left == null && right == null;
	}
}
